Namespacing everything to /UVa.
[andmenj-acm.git] / UVa / 11451 - Water restrictions / 11451.2.cpp
blob91d878c275c2aaee8db44e400c0e59114b340930
1 #include <iostream>
2 #include <cassert>
3 #include <vector>
5 using namespace std;
7 int pos[10], m[10], n[10], C, best, S;
9 //int cantidad = 0;
11 void backtrack(){
12 //cantidad++;
14 for (int i=0, sum = 0; i<S; ++i){
15 sum += n[i];
16 if (sum > C) return;
19 int mask = 0;
20 for (int i=0; i<S; ++i){
21 if (n[i] > 0){
22 for (int j=pos[i]-n[i]; j<= pos[i]+n[i]; ++j){
23 mask = mask | (1<<j);
28 best >?= __builtin_popcount(mask);
30 for (int i=0; i<S; ++i){
31 if (n[i]+1 <= m[i]){
32 n[i]++;
33 backtrack();
34 n[i]--;
39 int main(){
40 int T;
41 cin >> T;
42 while (T--){
43 int L;
44 cin >> L >> S;
45 for (int i=0; i<S; ++i){
46 cin >> pos[i];
48 cin >> C;
49 assert(C <= 11);
50 for (int i=0; i<S; ++i){
51 cin >> m[i];
54 best = -1;
55 //cantidad = 0;
56 for (int i=0; i<S; ++i){
57 n[i] = 0;
59 //backtrack();
60 cout << best << endl;
61 //cout << "Evalué " << cantidad << " opciones.\n";
64 return 0;